package skip_list

import (
	"math/rand"
	"time"
)

const MaxLevel = 32

func init() {
	rand.Seed(time.Now().Unix())
}

type MSkipNode struct {
	score   int
	value   interface{}
	forward []*MSkipNode
}

func NewMSkipNode(level int, score int, value interface{}) *MSkipNode {
	return &MSkipNode{
		score:   score,
		value:   value,
		forward: make([]*MSkipNode, level),
	}
}

type MSkipList struct {
	header *MSkipNode
	level  int
	length int
}

func NewMSkipList() *MSkipList {
	return &MSkipList{
		header: NewMSkipNode(MaxLevel, 0, 0),
		level:  0,
	}
}

func getRandLevel() int {
	var val int = 1;
	for rand.Int()%2 == 0 {
		val++
	}
	if val >= MaxLevel {
		return MaxLevel
	} else {
		return val
	}
}

func (s *MSkipList) GetElem(score int) (interface{}, bool) {
	var q *MSkipNode //当前score元素
	var p *MSkipNode //当前score前一个元素

	//从最高层开始搜
	p = s.header
	for ii := s.level - 1; ii >= 0; ii-- {
		for {
			q = p.forward[ii]
			if q != nil && q.score < score {
				p = q
			} else if q != nil && q.score == score {
				return q.value, true
			} else {
				break
			}
		}
	}
	return nil, false
}

func (s *MSkipList) DeleteElem(score int) bool {
	update := make([]*MSkipNode, MaxLevel)
	var q *MSkipNode //当前score元素
	var p *MSkipNode //当前score前一个元素

	//从最高层开始搜
	p = s.header
	for ii := s.level - 1; ii >= 0; ii-- {
		for {
			q = p.forward[ii]
			if q != nil && q.score < score {
				p = q
			} else {
				break
			}
		}
		update[ii] = p
	}

	if q == nil || q.score != score {
		return false
	}

	//逐层删除，和普通列表删除一样
	for jj := s.level - 1; jj >= 0; jj-- {
		if update[jj].forward[jj] == q {
			update[jj].forward[jj] = q.forward[jj]
		}
	}

	//如果删除的是最大层的节点，那么需要重新维护跳表的
	for jj := s.level - 1; jj >= 0; jj-- {
		if s.header.forward[jj] == nil {
			s.level--
		}
	}
	s.length--
	return true
}

func (s *MSkipList) InsertElem(score int, value interface{}) bool {
	update := make([]*MSkipNode, MaxLevel)
	var q *MSkipNode //当前score元素
	var p *MSkipNode //当前score前一个元素

	//从最高层开始搜
	p = s.header
	for ii := s.level - 1; ii >= 0; ii-- {
		for {
			q = p.forward[ii]
			if q != nil && q.score < score {
				p = q
			} else {
				break
			}
		}
		update[ii] = p
	}

	if q != nil && q.score == score {
		return false
	}

	//产生一个随机层数
	level := getRandLevel()
	if level > s.level {
		for jj := s.level; jj < level; jj++ {
			update[jj] = s.header
		}
		s.level = level
	}

	//新建一个待插入节点q
	nNode := NewMSkipNode(level, score, value)

	//一层一层插入
	for ll := 0; ll < level; ll++ {
		nNode.forward[ll] = update[ll].forward[ll]
		update[ll].forward[ll] = nNode
	}
	s.length++
	return true
}

func (s *MSkipList) Traverse() {
	for ii := s.level - 1; ii >= 0; ii-- {
		print(ii, ":")
		q := s.header.forward[ii]
		for q != nil {
			print(q.score, "-", q.value.(int), ",")
			q = q.forward[ii]
		}
		println("")
	}
}
